{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Length of String After Deleting Similar Ends"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除字符串两端相同字符后的最短长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个只包含字符 <code>'a'</code>，<code>'b'</code> 和 <code>'c'</code> 的字符串 <code>s</code> ，你可以执行下面这个操作（5 个步骤）任意次：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>选择字符串 <code>s</code> 一个 <strong>非空</strong> 的前缀，这个前缀的所有字符都相同。</li>\n",
    "\t<li>选择字符串 <code>s</code> 一个 <strong>非空</strong> 的后缀，这个后缀的所有字符都相同。</li>\n",
    "\t<li>前缀和后缀在字符串中任意位置都不能有交集。</li>\n",
    "\t<li>前缀和后缀包含的所有字符都要相同。</li>\n",
    "\t<li>同时删除前缀和后缀。</li>\n",
    "</ol>\n",
    "\n",
    "<p>请你返回对字符串 <code>s</code> 执行上面操作任意次以后（可能 0 次），能得到的 <strong>最短长度</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"ca\"\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>你没法删除任何一个字符，所以字符串长度仍然保持不变。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"cabaabac\"\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>最优操作序列为：\n",
    "- 选择前缀 \"c\" 和后缀 \"c\" 并删除它们，得到 s = \"abaaba\" 。\n",
    "- 选择前缀 \"a\" 和后缀 \"a\" 并删除它们，得到 s = \"baab\" 。\n",
    "- 选择前缀 \"b\" 和后缀 \"b\" 并删除它们，得到 s = \"aa\" 。\n",
    "- 选择前缀 \"a\" 和后缀 \"a\" 并删除它们，得到 s = \"\" 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"aabccabba\"\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>最优操作序列为：\n",
    "- 选择前缀 \"aa\" 和后缀 \"a\" 并删除它们，得到 s = \"bccabb\" 。\n",
    "- 选择前缀 \"b\" 和后缀 \"bb\" 并删除它们，得到 s = \"cca\" 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 只包含字符 <code>'a'</code>，<code>'b'</code> 和 <code>'c'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-length-of-string-after-deleting-similar-ends](https://leetcode.cn/problems/minimum-length-of-string-after-deleting-similar-ends/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-length-of-string-after-deleting-similar-ends](https://leetcode.cn/problems/minimum-length-of-string-after-deleting-similar-ends/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ca\"', '\"cabaabac\"', '\"aabccabba\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        while i < j and s[i] == s[j]:\n",
    "            if s[i] == s[j]:\n",
    "                h = s[i]\n",
    "                while i < j and s[i] == h:\n",
    "                    i += 1\n",
    "                while i <= j and s[j] == h:\n",
    "                    j -= 1\n",
    "        return j - i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        m = 0\n",
    "        n = len(s) - 1\n",
    "        while m < n:\n",
    "            if s[n] != s[m]:\n",
    "                break\n",
    "            if m + 1 < n and s[m] == s[m+1]:\n",
    "                m += 1\n",
    "                continue\n",
    "            if n -1 > m and s[n] == s[n-1]:\n",
    "                n -= 1\n",
    "                continue\n",
    "            m += 1\n",
    "            n -= 1\n",
    "            \n",
    "        return n-m+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        l, r = 0, len(s) - 1\n",
    "        while l < r:\n",
    "            if s[l] == s[r]:\n",
    "                left, right = s[l], s[r]\n",
    "                while l < r and s[l] == left:\n",
    "                    l += 1\n",
    "                while r > 0 and s[r] == right:\n",
    "                    r -= 1\n",
    "            else:\n",
    "                break\n",
    "        if l > r:\n",
    "            return 0\n",
    "        return r - l + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            if s[l] == s[r]:\n",
    "                while l + 1 < r and s[l + 1] == s[l]:\n",
    "                    l += 1\n",
    "                while l < r - 1 and s[r - 1] == s[r]:\n",
    "                    r -= 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            else:\n",
    "                break\n",
    "        return r - l + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left,right=0,len(s)-1\n",
    "        while left<right and s[left]==s[right]:\n",
    "            c=s[left]\n",
    "            left+=1\n",
    "            right-=1\n",
    "            while left<=right and s[left]==c: left+=1\n",
    "            while left<right and s[right]==c: right-=1\n",
    "        return right-left+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        # 双指针\n",
    "        l = 0\n",
    "        r = len(s) - 1\n",
    "        while l < r and s[l] == s[r]:\n",
    "            l += 1\n",
    "            r -= 1\n",
    "            while l <= r and s[l] == s[l - 1]:\n",
    "                l += 1\n",
    "            while l <= r and s[r] == s[r + 1]:\n",
    "                r -= 1\n",
    "        \n",
    "        return r - l + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right and s[left] == s[right]:\n",
    "            c = s[left]\n",
    "            while left <= right and s[left] == c:\n",
    "                left += 1\n",
    "            while right >= left and s[right] == c:\n",
    "                right -= 1\n",
    "        return right - left + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s)-1\n",
    "        while(left < right):\n",
    "            if(s[left] != s[right]):\n",
    "                return right - left + 1\n",
    "            i = left + 1\n",
    "            while(i < right and s[i] == s[left]):\n",
    "                i += 1\n",
    "            left = i\n",
    "            j = right  - 1\n",
    "            while(j > left and s[j] == s[right]):\n",
    "                j -= 1\n",
    "            right = j\n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        p1 = 0\n",
    "        p2 = n-1\n",
    "        while p2 > p1 and s[p1] == s[p2]:\n",
    "            while p1 < p2 and s[p1] == s[p1 + 1]:\n",
    "                p1 += 1\n",
    "            while p2 > p1 and s[p2] == s[p2-1]:\n",
    "                p2 -= 1\n",
    "            if p1 == p2:\n",
    "                return 0\n",
    "            else:\n",
    "                p1 += 1\n",
    "                p2 -= 1\n",
    "        return p2 - p1 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        l=0\n",
    "        r=len(s)-1\n",
    "        while l<r and s[l]==s[r]:\n",
    "            t=s[l]\n",
    "            while l<=r and s[l]==t:\n",
    "                l+=1\n",
    "            while l<=r and s[r]==t:\n",
    "                r-=1\n",
    "        return r-l+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s)-1\n",
    "        while left<right:\n",
    "            if s[left] != s[right]:\n",
    "                break\n",
    "            char = s[left]\n",
    "            while left<=right and s[left]==char:\n",
    "                left += 1\n",
    "            while right>=left and s[right]==char:\n",
    "                right -= 1\n",
    "\n",
    "        return right-left+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right and s[left] == s[right]:\n",
    "            c = s[left]\n",
    "            while left <= right and s[left] == c:\n",
    "                left += 1\n",
    "            while right >= left and s[right] == c:\n",
    "                right -= 1\n",
    "        return right - left + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j and s[i] == s[j]:\n",
    "            pre = s[i]\n",
    "            while i < j and s[i] == pre:\n",
    "                i += 1\n",
    "            i -= 1\n",
    "            post = s[j]\n",
    "            while i < j and s[j] == post:\n",
    "                j -= 1\n",
    "            j += 1\n",
    "            if s[i] == s[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "        return j - i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left = 0\n",
    "        right = len(s) - 1\n",
    "        while left < right and s[left] == s[right]:\n",
    "            while left + 1 < right and s[left + 1] == s[left]:\n",
    "                left += 1\n",
    "            while left < right - 1 and s[right - 1] == s[right]:\n",
    "                right -= 1\n",
    "            left, right = left + 1, right - 1\n",
    "        return right - left + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i = 0\n",
    "        j = len(s)-1 \n",
    "        while i<j:\n",
    "            if s[i] == s[j]:\n",
    "                while i<j and s[i]==s[j]:\n",
    "                    i+=1\n",
    "                while i-1<j and s[i-1]==s[j]:\n",
    "                    j -= 1\n",
    "            else:\n",
    "                break\n",
    "        return j+1-i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            left = 0\n",
    "            right = n - 1\n",
    "            while left < right:\n",
    "                if s[left] == s[right]:\n",
    "                    while left < right and s[left] == s[left + 1]:\n",
    "                        left += 1\n",
    "                    while left < right and s[right] == s[right - 1]:\n",
    "                        right -= 1\n",
    "                    if left == right:\n",
    "                        if s[left] == s[left - 1]:\n",
    "                            return 0\n",
    "                        else:\n",
    "                            return 1\n",
    "                    left+=1\n",
    "                    right-=1\n",
    "                else:\n",
    "                    break\n",
    "            s = s[left :right+1]\n",
    "            return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j and s[i] == s[j]:\n",
    "            while i + 1 < j and s[i] == s[i + 1]:\n",
    "                i += 1\n",
    "            while i < j - 1 and s[j - 1] == s[j]:\n",
    "                j -= 1\n",
    "            i, j = i + 1, j - 1\n",
    "        return max(0, j - i + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left=0\n",
    "        right=len(s)-1\n",
    "        while left<right and s[left]==s[right]:\n",
    "            c=s[left]\n",
    "            while left<=right and s[left]==c:\n",
    "                left+=1\n",
    "            while right>=left and s[right]==c:\n",
    "                right-=1\n",
    "        return right-left+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left = 0\n",
    "        right = len(s) - 1\n",
    "        while left < right:\n",
    "            if s[left] == s[right]:\n",
    "                tmp = s[left]\n",
    "                while left < right and s[left] == tmp:\n",
    "                    left += 1\n",
    "                if left == right: \n",
    "                    return 0\n",
    "                while left < right and s[right] == tmp:\n",
    "                    right -= 1\n",
    "            else:\n",
    "                break\n",
    "        if left == right:\n",
    "            return 1\n",
    "        return right - left + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right and s[left] == s[right]:\n",
    "            c = s[left]\n",
    "            while left <= right and s[left] == c:\n",
    "                left += 1\n",
    "            while right >= left and s[right] == c:\n",
    "                right -= 1\n",
    "        return right - left + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s)-1\n",
    "        while(left < right):\n",
    "            if(s[left] != s[right]):\n",
    "                return right - left + 1\n",
    "            i = left + 1\n",
    "            while(i < right and s[i] == s[left]):\n",
    "                i += 1\n",
    "            left = i\n",
    "            j = right  - 1\n",
    "            while(j > left and s[j] == s[right]):\n",
    "                j -= 1\n",
    "            right = j\n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left=0\n",
    "        right = len(s)-1\n",
    "        while left<right:\n",
    "            char = s[left]\n",
    "            if s[left]==s[right]:\n",
    "                while s[left]==char:\n",
    "                    left+=1\n",
    "                    if left>=len(s):\n",
    "                        break\n",
    "                while s[right]==char:\n",
    "                    if right<0:\n",
    "                        break\n",
    "                    right-=1\n",
    "            else:\n",
    "                break\n",
    "        return max(right-left+1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s)-1\n",
    "        while(left < right):\n",
    "            if(s[left] != s[right]):\n",
    "                return right - left + 1\n",
    "            i = left + 1\n",
    "            while(i < right and s[i] == s[left]):\n",
    "                i += 1\n",
    "            left = i\n",
    "            j = right  - 1\n",
    "            while(j > left and s[j] == s[right]):\n",
    "                j -= 1\n",
    "            right = j\n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        if i == j:\n",
    "            return 1\n",
    "        while s[i] == s[j]:\n",
    "            ch = s[i]\n",
    "            while s[i] == ch and i < j:\n",
    "                i += 1\n",
    "            if i == j:\n",
    "                return 0\n",
    "            while s[j] == ch and i < j:\n",
    "                j -= 1\n",
    "            if i == j:\n",
    "                return 1\n",
    "        return j + 1 - i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        p, q = 0, n - 1\n",
    "        while p < q:\n",
    "            if s[p] == s[q]:\n",
    "                while p < q and s[p + 1] == s[p]:\n",
    "                    p += 1\n",
    "                p += 1\n",
    "                while p < q and s[q - 1] == s[q]:\n",
    "                    q -= 1\n",
    "                q -= 1\n",
    "                if p == q:\n",
    "                    return 1\n",
    "            else:\n",
    "                return q - p + 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left = 0\n",
    "        right = len(s)-1\n",
    "        while left<right and s[left]==s[right]:\n",
    "            c = s[left]\n",
    "            while left<=right and s[left]==c:\n",
    "                left += 1\n",
    "            while left<=right and s[right]==c:\n",
    "                right -= 1\n",
    "        return right-left+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left<right and s[left] == s[right]:\n",
    "            sign = s[left]\n",
    "            while  left<=right and s[left] == sign:\n",
    "                left += 1\n",
    "            while left<=right and s[right] == sign:\n",
    "                right -= 1\n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        # 双指针\n",
    "        l = 0\n",
    "        r = len(s) - 1\n",
    "        while l < r and s[l] == s[r]:\n",
    "            l += 1\n",
    "            r -= 1\n",
    "            while l <= r and s[l] == s[l - 1]:\n",
    "                l += 1\n",
    "            while l <= r and s[r] == s[r + 1]:\n",
    "                r -= 1\n",
    "        \n",
    "        return r - l + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        # while True:\n",
    "        #     if not s or len(s) == 1 or s[0] != s[-1]:\n",
    "        #         break\n",
    "        #     else:\n",
    "        #         ch = s[0]\n",
    "        #         s = s.strip(ch)\n",
    "        # return len(s)\n",
    "\n",
    "        n = len(s)\n",
    "        left, right = 0, n - 1\n",
    "        while True:\n",
    "            if right - left < 1 or s[left] != s[right]:\n",
    "                return right - left + 1\n",
    "            else:\n",
    "                ch = s[left]\n",
    "                while right - left >= 1 and s[left] == ch:\n",
    "                    left += 1\n",
    "                if right == left:\n",
    "                    return 0\n",
    "                while right - left >= 1 and s[right] == ch:\n",
    "                    right -= 1\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j and s[i] == s[j]:\n",
    "            pre = s[i]\n",
    "            while i <= j and s[i] == pre:\n",
    "                i += 1\n",
    "            while i <= j and s[j] == pre:\n",
    "                j -= 1\n",
    "        return j - i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j and s[i] == s[j]:\n",
    "            while i + 1 < j and s[i] == s[i + 1]:\n",
    "                i += 1\n",
    "            while i < j - 1 and s[j - 1] == s[j]:\n",
    "                j -= 1\n",
    "            i, j = i + 1, j - 1\n",
    "        return max(0, j - i + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        # 双指针\n",
    "        l = 0\n",
    "        r = len(s) - 1\n",
    "        while l < r and s[l] == s[r]:\n",
    "            l += 1\n",
    "            r -= 1\n",
    "            while l <= r and s[l] == s[l - 1]:\n",
    "                l += 1\n",
    "            while l <= r and s[r] == s[r + 1]:\n",
    "                r -= 1\n",
    "        \n",
    "        return r - l + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        while True:\n",
    "            x, y = s[i], s[j]\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if x != y:\n",
    "                return j - i + 1\n",
    "            else:\n",
    "                while i < len(s) - 1 and s[i+1] == x:\n",
    "                    i += 1\n",
    "                while j > 0 and s[j-1] == y:\n",
    "                    j -= 1\n",
    "                if i > j:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    i += 1\n",
    "                    j -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i, j =0, n-1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return j-i+1\n",
    "            while i+1<n and s[i+1] == s[i]:\n",
    "                i += 1\n",
    "            \n",
    "            while j-1>=0 and s[j-1] == s[j]:\n",
    "                j -= 1\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            i += 1\n",
    "            j -= 1\n",
    "                \n",
    "\n",
    "        return j-i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i, j = 0, len(s)-1\n",
    "        while i < j:\n",
    "            while i < j and s[i] == s[j]:\n",
    "                i += 1\n",
    "            while 0 < i <= j and s[j] == s[i-1]:\n",
    "                j -= 1\n",
    "            if s[i] != s[j]:\n",
    "                break\n",
    "        if i > j:\n",
    "            return 0\n",
    "        return j-i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength (self, s: str) -> int:\n",
    "        i, j = 0, len (s) - 1\n",
    "        while i < j and s [i] == s [j]:\n",
    "            while i + 1 < j and s [i] == s [i + 1]:\n",
    "                i += 1\n",
    "            while i < j - 1 and s [j - 1] == s [j]:\n",
    "                j -= 1\n",
    "            i, j = i + 1, j - 1\n",
    "        return max (0, j - i + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i, j = 0, len(s)-1\n",
    "        while i < j:\n",
    "            while i < j and s[i] == s[j]:\n",
    "                i += 1\n",
    "            while 0 < i <= j and s[j] == s[i-1]:\n",
    "                j -= 1\n",
    "            if s[i] != s[j]:\n",
    "                break\n",
    "        if i > j:\n",
    "            return 0\n",
    "        return j-i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        '''\n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        while True:\n",
    "            x, y = s[i], s[j]\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if x != y:\n",
    "                return j - i + 1\n",
    "            else:\n",
    "                while i < len(s) - 1 and s[i+1] == x:\n",
    "                    i += 1\n",
    "                while j > 0 and s[j-1] == y:\n",
    "                    j -= 1\n",
    "                if i > j:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "        '''\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right and s[left] == s[right]:\n",
    "            c = s[left]\n",
    "            while left <= right and s[left] == c:\n",
    "                left += 1\n",
    "            while right >= left and s[right] == c:\n",
    "                right -= 1\n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right:\n",
    "            if s[left] == s[right]:\n",
    "                while left < right and s[left] == s[left + 1]:\n",
    "                    left += 1\n",
    "                while left < right and s[right] == s[right - 1]:\n",
    "                    right -= 1\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return 0 if right < left else right - left + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        l, r = 0, len(s) - 1\n",
    "        while l < r and s[l] == s[r]:\n",
    "            c = s[l]\n",
    "            while l <= r and s[l] == c:\n",
    "                l += 1\n",
    "            while l <= r and s[r] == c:\n",
    "                r -= 1\n",
    "        return r - l + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right and s[left] == s[right]:\n",
    "            c = s[left]\n",
    "            while left <= right and s[left] == c:\n",
    "                left += 1\n",
    "            while right >= left and s[right] == c:\n",
    "                right -= 1\n",
    "        return right - left + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right and s[left] == s[right]:\n",
    "            c = s[left]\n",
    "            while left <= right and s[left] == c:\n",
    "                left += 1\n",
    "            while right >= left and s[right] == c:\n",
    "                right -= 1\n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        if s is None or len(s) == 0:\n",
    "            return 0\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        \n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        t = None\n",
    "        while i < j:\n",
    "            t = i\n",
    "            while i <= j and s[i] == s[t]:\n",
    "                i += 1\n",
    "            \n",
    "            d = j\n",
    "            while i <= j and s[j] == s[t]:\n",
    "                j -= 1\n",
    "            \n",
    "            if d == j:\n",
    "                if i > j and i - t >= 2:\n",
    "                    return 0\n",
    "                elif i > j:\n",
    "                    return 1\n",
    "                # i <= j\n",
    "                return d + 1 - t\n",
    "            \n",
    "        return 1\n",
    "        \n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        if len(s) < 2:\n",
    "            return 1\n",
    "        if len(s) == 2:\n",
    "            return 0 if s[0] == s[1] else 2\n",
    "        m = 0\n",
    "        n = len(s) - 1\n",
    "        while m < n:\n",
    "            if s[n] != s[m]:\n",
    "                break\n",
    "            if m + 1 < n and s[m] == s[m+1]:\n",
    "                m += 1\n",
    "                continue\n",
    "            if n -1 > m and s[n] == s[n-1]:\n",
    "                n -= 1\n",
    "                continue\n",
    "            m += 1\n",
    "            n -= 1\n",
    "            \n",
    "        return n-m+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right and s[left] == s[right]:\n",
    "            tmp = s[left]\n",
    "            while left <= right and s[left] == tmp:\n",
    "                left += 1\n",
    "            while left <= right and s[right] == tmp:\n",
    "                right -= 1\n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        while True:\n",
    "            if length <= 1:\n",
    "                return length\n",
    "            elif length == 2:\n",
    "                if s[0] == s[1]:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    return length\n",
    "            else:\n",
    "                char = s[0]\n",
    "                token_start = 0\n",
    "                token_end = 0\n",
    "                for i in range(length):\n",
    "                    if s[i] == char:\n",
    "                        continue\n",
    "                    else:\n",
    "                        token_start = i - 1\n",
    "                        break\n",
    "                for j in range(length-1,0,-1):\n",
    "                    if s[j] == char:\n",
    "                        continue\n",
    "                    else:\n",
    "                        token_end = j + 1\n",
    "                        break\n",
    "                if token_start >= token_end:\n",
    "                    return 0\n",
    "                elif token_end > length-1:\n",
    "                    return length\n",
    "                else:\n",
    "                    s = s[token_start+1 : token_end]\n",
    "                    length = len(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i,j = 0, len(s)-1\n",
    "        while i<j:\n",
    "            c=s[i]\n",
    "            if s[j]!=c:\n",
    "                break\n",
    "            while i<j and s[i]==c:\n",
    "                i+=1\n",
    "            while i<=j and s[j]==c:\n",
    "                j-=1\n",
    "        return j+1-i if i<=j else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j and s[i] == s[j]:\n",
    "            while i + 1 < j and s[i] == s[i + 1]:\n",
    "                i += 1\n",
    "            while i < j - 1 and s[j - 1] == s[j]:\n",
    "                j -= 1\n",
    "            i, j = i + 1, j - 1\n",
    "        return max(0, j - i + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLength(self, s: str) -> int:\n",
    "        while True:\n",
    "            if not s or len(s) == 1 or s[0] != s[-1]:\n",
    "                break\n",
    "            else:\n",
    "                ch = s[0]\n",
    "                s = s.strip(ch)\n",
    "        return len(s)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
